This invention relates to the compression of still or motion images for efficient storage and/or transmission. Most frequently used is the method of performing the Discrete Cosine Transform (DCT) followed by a quantization of the resulting transform coefficients to minimize coefficient data that must be transmitted to represent the imagery and lastly a lossless entropy encoding process for transmission of the quantized data. This prior art sequence of operations is well known and readily implemented. The DCT is a blocked transform wherein individual blocks usually of an eight-by-eight array of picture elements each can be individually processed before moving on to process the next block.
A natural consequence of the quantization process is the loss of coefficient accuracy at the decoder, which results in distortion of the reconstructed imagery. The purpose of a good transform is to minimize the appearance of the distortion introduced to create the efficient compression of the imagery. The DCT is an excellent transform to accomplish this goal. However, when a large amount of compression is achieved by using a large amount of quantization then noticeable artifacts appear in the reconstructed imagery. Most bothersome is the so-called blocking artifact, which causes image portions to appear in blocks or tiles.
The Wavelet Transform (WT) is also used for image compression and does not suffer the blocking problem since it is calculated as overlapping waves without the immediate borders of the blocked transforms. The blocked nature of the DCT, on the other hand, makes it ideal for the motion compensated prediction process used in the Interframe compression of moving imagery. Use of this Inter-frame compression technique with the Wavelet Transform is problematic and not generally undertaken. For single images the Wavelet Transform provides high compression efficiency without blocking problems although its calculation method is generally more complex than that of the DCT.
An early example of WT prior art is described in U.S. Pat. No. 4,447,886 named, Triangle and Pyramid Signal Transforms and Apparatus issued to Meeker. Overlapping basis functions are described to form a compact representation of one- and two-dimensional data sets. Said two-dimensional representation uses the one-dimensional transform in a modified separable two-dimensional configuration. These transforms are shown in a stand-alone implementation not in conjunction with another transform. The transforms have some characteristics similar to the one-dimensional Wavelet transform used in the present invention. The two-dimensional Wavelet Transform introduced herein and described is a novel non-separable transform that is an integral part of this present invention.
Block edge artifacts occurring with DCT reconstruction have been treated in some system standards for many years with smoothing filters applied across the block boundaries. Although effective in reducing the artifacts themselves the filtering action can attenuate actual image detail. Moreover, the edge smoothing process can change the average brightness of a block. In motion imagery this can cause an unintended wavy appearance of imagery undergoing translational motion. In the earlier H.261 video codec for teleconferencing applications the smoothing filter was a simple low-pass filter across the block edges but has grown in complexity with more recent standards. The newer H.264 codec uses between three and five tap filters to adjust the degree of filtering under a variety of circumstances. Details of the H.264 de-blocking filter are found in “H.264 and MPEG-4 Video Compression” by lain E. G. Richardson, Wiley, 2004, PP. 184-187.
Another prior art technique is “Prediction of AC Coefficients from the DC Values” in the firstJoint Photographic Experts Group (JPEG) standard. This method is included in the specification ISO/IECJTC1/SC2/WG8 N745 (May 1988). A description is also given in “JPEG Still Image Data Compression Standard”, VanNostrand Reinhold, N.Y., 1993, pp. 261-265. by W. B. Pennebaker and J. L. Mitchell. The method predicts the first five AC DCT coefficients of a block being processed using the model of a quadratic surface fitted to a three-by-three array of DCT blocks where the block presently being processed is at the center. With this method a smooth surface is produced at the center block's edges in smooth background areas of the image. However, predictions are not reliable at edges and the method must be avoided in those blocks where transmitted ac. coefficients are decoded.
Another technique directed to block artifact reduction is “Method and system for adapting a digitized signal processing system for block processing with minimal blocking artifacts” described in U.S. Pat. No. 4,754,492 by Malvar. This uses multiple DCT blocks with a post-filtering process forming, in essence, a basis function that is twice, or more, the length of DCT functions and is called the Lapped Orthogonal Transform (LOT). Blocks therefore overlap each other by 50%, or more. LOT cosine basis functions both start and end at the value of zero whereas the comparable DCT functions start and end near the cosine function's maximum value. Discontinuities at the border between blocks are therefore avoided. The meaning of the transform coefficients are modified from that of standard blocked transforms such that the amplitudes of the discrete frequencies is carried by the lower half of the frequencies in a pair of one-dimensional blocks leaving the upper half of the discrete frequencies to carry information as to how the actual frequency components are distributed between the blocks of the pair. Quantization effects instead relate to unintended distribution of frequency content between the pair sometimes producing a “ringing” effect.
U.S. Pat. No. 5,220616 by Downing, et al describes a method operating on reconstructed imagery at the decoder transformed from received quantized transform coefficients wherein the resulting block boundaries are sequentially scanned and subsequently smoothed by a one-dimensional operator matrix.
U.S. Pat. No. 5,357,584 by Yamaoka discloses a method for evaluating at the encoder the block artifact effects that will occur at the decoder for particular levels of encoder quantization. The encoder is then able to use an optimum degree of coefficient quantization balancing image quality and compression efficiency.
U.S. Pat. No. 5,367,385 by Yuan discloses a method for pixel modification around block boundaries of imagery reconstructed from blocked transforms. A low-pass filtering is applied to reduce the difference between pixels across block boundaries.
U.S. Pat. No. 5,629,778 issued to Reuman that discloses a method for suppressing block artifacts through use of overlap transformation of reconstructed imagery at the decoder and a means of filtering in the frequency domain using a quantization error matrix. Said error matrix is derived from additional data sent from the encoder or from an estimation of error via a decoder look-up table. The adjusted overlap frequency representation is then inverse-transformed to obtain reduced-noise imagery for presentation.
The prior art in many cases has approached the block artifact problem in a two step process of first measuring the discontinuities at block edges in either the data or the frequency domain caused by quantization effects on the transform coefficients received at the decoder. The second step is a compensation process involving replacement of data values on either side of a block edge or the addition of compensating frequency domain coefficients to affect a similar result.
The present invention differs from this approach and does not rely on measurement of block edges or subsequent compensation of them. For small to moderate values of coefficient quantization a primary result is the loss of transform coefficients that are quantized to the value of zero. A primary category of these lost coefficients is a pattern that also appears in adjacent blocks. In combination these transform coefficients indicate low-frequency components of the same wave over multiple blocks. The method of the new invention largely prevents the loss of these low-frequency components over multiple blocks by re-purposing the dc. coefficients of the block transform to signal said components to the decoder. Since the dc. component is not subject to variable quantization as are the ac. transform coefficients in standardized systems the quantization effects do not occur with this signaling. The re-purposing is accomplished by replacement of the dc. term of the blocked transform with a Wavelet Transform scaled coefficient having certain desirable coefficients designed for this purpose. A combination of the Wavelet coefficients for multiple blocks by itself results in a decoder reconstruction of smooth contour without block edges. This technique also lessens artifacts caused by the ac, block transform coefficients remaining to be transmitted to generate detail in each block. This re-purposing method offers greater use of the already available signaling structure in current image compression systems and does not require any further signaling of image data, error data or side information.